import common.ListNode;

public class Test2 {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if(head == null || head.next == null || m == n) {
            return head;
        }
        // 新建头节点
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        // 计算需要反转的节点个数
        int index = n - m + 1;
        ListNode cur = newHead;
        while(m > 1) {
            m--;
            cur = cur.next;
        }
        // 此时 cur 表示的节点是 m 的前一个节点
        // 需要反转的区间的头节点
        ListNode shead = null;
        ListNode curNext = cur.next;
        while(curNext != null && index-- != 0) {
            ListNode tmp = curNext.next;
            curNext.next = shead;
            shead = curNext;
            curNext = tmp;
        }
        // 此时 curNext 就是 n + 1 的节点
        cur.next.next = curNext;
        cur.next = shead;
        return newHead.next;
    }
}